1079. 活字印刷【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 回溯

1. 📝 题目描述

• leetcode

你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

---

注意：本题中，每个活字字模只能使用一次。

---

示例 1：

输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

示例 2：

输入："AAABBC"
输出：188

示例 3：

输入："V"
输出：1

---

提示：

• 1 <= tiles.length <= 7
• tiles 由大写英文字母组成

2. 🎯 s.1 - 回溯

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {string} tiles
 * @return {number}
 */
var numTilePossibilities = function (tiles) {
  const count = new Array(26).fill(0)
  for (const ch of tiles) count[ch.charCodeAt(0) - 65]++
  let res = 0
  function dfs() {
    for (let i = 0; i < 26; i++) {
      if (count[i] === 0) continue
      res++
      count[i]--
      dfs()
      count[i]++
    }
  }
  dfs()
  return res
}

• 时间复杂度：$O(n!)$，其中 $n$ 是 tiles 的长度
• 空间复杂度：$O(n)$，递归栈深度

算法思路：

• 统计每个字母的出现次数，用回溯法枚举所有非空序列
• 每一层遍历 26 个字母，若剩余次数 > 0 则选取并递归
• 由于按字母计数而非按位置枚举，自然避免了重复序列